/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    ListNode *doubleIt(ListNode *head)
    {
        vector<ListNode *> nodes;
        ListNode *p = head;
        while (p != nullptr)
        {
            nodes.push_back(p);
            p = p->next;
        }
        int n = nodes.size();
        bool carry = false;
        for (int i = n - 1; i >= 0; --i)
        {
            int digit = nodes[i]->val * 2 + carry;
            nodes[i]->val = digit % 10;
            carry = digit / 10;
        }
        if (carry)
        {
            ListNode *newHead = new ListNode();
            newHead->val = 1;
            newHead->next = head;
            return newHead;
        }
        return head;
    }
};